package com.sword.onlysword.games;

import com.sword.onlysword.entity.Sudoku;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * com.sword.onlysword.games.Sudoku
 * Created by SwordLiu on 2018-02-03.
 */
public class SudokuBuilder {

    //第一部分代码，通过回溯法随机生成符合九宫格规则的九宫格
    //用回溯法随机生成九宫格（此处只生成一个九宫格），
    // bl用来作为标记，当随机生成第一个九宫格时，将bl置为true，然后结束回溯。
    //jiuGongGe作为临时储存随机生成的九宫格，当回溯法结束时，jiuGongGe将会变为初始状态；
    // end_jiuGongGe用来储存最终随机生成的九宫格
    private int jiuGongGe[][] = new int[9][9];
    private Boolean bl = false;
    private int end_jiuGongGe[][] = new int[9][9];
    /**
     * 难度：0=菜鸟，1=初级，2=中级，3=高级，4=骨灰级
     * 默认：初级
     */
    private int difficulty = 1;
    private List<Integer> difficultyArr = Arrays.asList(0, 1, 2, 3, 4);

    /**
     * 生成难度模型
     * @param difficulty
     * @return
     */
    private int difficultyModel(int difficulty) {
        //如果输入难度无效，则以默认难度输出模型
        difficulty = difficultyArr.contains(difficulty) ? difficulty : this.difficulty;
        Double model;
        switch (difficulty) {
            case 0:
                model = Math.random() * 16 + 1;//菜鸟级：1-16个空白
                break;
            case 2:
                model = Math.random() * 17 + 34;//中级：34-50个空白
                break;
            case 3:
                model = Math.random() * 17 + 51;//高级：51-67个空白
                break;
            case 4:
                model = Math.random() * 13 + 68;//骨灰：68-80个空白
                break;
            default:
                model = Math.random() * 17 + 17;//初级：17-33个空白
        }
        return model.intValue();
    }

    /**
     * 判断在九宫格中的坐标(x,y)的位置上插入value，是否符合规则
     *
     * @param x
     * @param y
     * @param value
     * @return
     */
    private Boolean legal(int a[][],int x, int y, int value) {

        for (int i = 0; i < 9; i++) {
            //如果列中有value，则返回false
            if (i != x && a[i][y] == value) {
                return false;
            }
            //如果行中有value，则返回false
            if (i != y && a[x][i] == value) {
                return false;
            }
        }

        //(minX,minY)是(x,y)所属小九宫格的左上角的坐标
        int minX = x / 3 * 3;
        int minY = y / 3 * 3;

        for (int i = minX; i < minX + 3; i++) {
            for (int j = minY; j < minY + 3; j++) {
                //如果小九宫格中的非(x,y)的坐标上的值为value，返回false
                if (i != x && j != y && a[i][j] == value) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * 随机生成九宫格的算法，通过回溯生成。
     *
     * @param k
     */
    private void generateJiugongGe(int k) {
        if (bl) {
            return;
        }
        if (k == 81) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(jiuGongGe[i][j] + " ");
                    end_jiuGongGe[i][j] = jiuGongGe[i][j];
                }
                System.out.println();
            }
            bl = true;
            return;
        }

        //取得第k+1个值所对应的坐标(x,y),k是从0开始的。
        int x = k / 9;
        int y = k % 9;

        if (jiuGongGe[x][y] == 0) {
            //index用来判断是否已经完全随机生成了1-9这个9个数
            int index = 0;
            while (index < 9) {
                //动态数组list用来储存已经随机生成的1-9的数字
                ArrayList list = new ArrayList(9);
                Random random = new Random();
                int i = random.nextInt(9) + 1;
                //当list中包含数字i时，在重新生成1-9的数字
                while (list.contains(i))
                    i = random.nextInt(9) + 1;
                list.add(i);
                index++;
                jiuGongGe[x][y] = i;
                //legal()函数是判断在九宫格中的坐标(x,y)的位置上插入i，是否符合规则
                if (legal(jiuGongGe,x, y, i)) {
                    generateJiugongGe(k + 1);
                }
            }
            jiuGongGe[x][y] = 0;     //回溯时，将坐标(x,y)的值置零

        } else {
            generateJiugongGe(k + 1);
        }
    }
    /**
     * 第二部分，通过第一部分生成的九宫格，根据难度模型数量置零，以此形成数独游戏。
     * @param model 难度模型
     * @return 数独游戏
     */
    private int[][] generateShuDu(int model){
        Random random=new Random();
        int num = 81 - model;
        List<Integer> list=new ArrayList<>(num);
        for (int i = 0; i < num ; i++) {
            int index=random.nextInt(81);
            while (list.contains(index)){
                index=random.nextInt(81);
            }
            list.add(index);
        }
        int shuDu[][]=new int[9][9];
        for (int i = 0; i <9 ; i++) {
            for (int j = 0; j <9 ; j++) {
                if(!list.contains(i*9+j)){
                    shuDu[i][j]=0;
                }else{
                    shuDu[i][j]=end_jiuGongGe[i][j];
                }
            }
        }
        return shuDu;
    }

    //第三部分，是针对第二部分生成的数独游戏，使用回溯法，实现对数独的解答。
    //shuDu[][]是用来存放数独游戏的二维数组。
    //numOfSolution是用来统计shuDu[][]中存放的数独游戏的解的个数
    private int shuDu[][] = new int[9][9];
    private int numOfSolution=1;

    /**
     *
     * @param shuDu
     */
    private void setShuDu(int[][] shuDu) {
        this.shuDu = shuDu;
    }

    /**
     * 回溯法求解数独，参考第一部分用回溯法随机生成数独的解空间的代码
     * @param k
     */
    private void shuDu_solution(int k) {

        if (k == 81) {
            System.out.println("解法"+numOfSolution);
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(shuDu[i][j] + " ");
                }
                System.out.println();
            }

            numOfSolution++;
            return;
        }
        int x = k / 9;
        int y = k % 9;
        if (shuDu[x][y] == 0) {
            for (int i = 1; i <= 9; i++) {
                shuDu[x][y] = i;
                if (legal(shuDu,x, y, i)) {
                    shuDu_solution(k + 1);
                }
            }
            shuDu[x][y] = 0;
        } else {
            shuDu_solution(k + 1);
        }
    }

    //打印二维数组a[m][n]
    private void displayArray(int a[][], int m, int n) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        SudokuBuilder sudoku = new SudokuBuilder();
        //第一部分的测试生成一个符合数独规则的九宫格
        System.out.println("第一部分的测试生成一个符合数独规则的九宫格");
        sudoku.generateJiugongGe(0);
        System.out.println();
        sudoku.displayArray(sudoku.end_jiuGongGe,9,9);

        System.out.println();

        //第二部分的测试，生成一个数独游戏，并输出该游戏
        System.out.println("第二部分的测试，生成一个数独游戏，并输出该游戏");
        System.out.println("----------------------------");
        System.out.println("生成数独");
        int generateShuDu[][]=sudoku.generateShuDu(46);
        sudoku.setShuDu(generateShuDu);
        sudoku.displayArray(sudoku.shuDu, 9, 9);

        System.out.println();

        //第三部分的测试，对数独游戏的解，并输出所有的解
        System.out.println("第三部分的测试，对数独游戏的解，并输出所有的解");
        System.out.println("----------------------------");
        System.out.println("shudu_solution");
        sudoku.shuDu_solution(0);
    }

    public static int[][] random(Sudoku param) {
        SudokuBuilder sudoku = new SudokuBuilder();
        sudoku.setDifficulty(param == null ? null : param.getDifficulty());
        sudoku.generateJiugongGe(0);
        int[][] generateShuDu = sudoku.generateShuDu(sudoku.difficultyModel(sudoku.difficulty));
        sudoku.setShuDu(generateShuDu);
        return sudoku.shuDu;
    }

    private void setDifficulty(Integer difficulty) {
        this.difficulty = difficulty == null ? this.difficulty : difficulty;
    }
}
